Mechanisms that provide various levels of QoS use schedulers and queues to offer privileged treatment or services to clients. These clients can vary from rental car customers waiting to be served in various queues depending on their membership level, to processes waiting to be executed on a computer . . . to packets belonging to various QoS classes waiting to be serviced by a router in a network.
In a queuing system, the clients with higher precedence classes have higher service rates or get serviced before the clients in the lower precedence classes. The privilege given to the clients in higher precedence classes causes a relatively shorter waiting time for them when compared to the clients in lower precedence classes. As a result, the clients in the higher precedence classes in general are able to leave the queuing system earlier than the clients in the lower precedence classes. To accomplish this, the queuing system often changes the sequence of clients to service the higher precedence clients before the lower precedence clients.
In some cases, when there are no clients with higher precedence classes waiting to be serviced, the queuing system may decide to “promote” a lower precedence class client to be serviced as a high precedence class client. This may be done to keep the efficiency high in the queuing system. In other cases, when a high precedence class is over-booked with clients then the queuing system may decide to “demote” a higher precedence class client to be serviced as a low precedence class client. After a queuing system “remarks” (promotes or demotes) a client, then there is a potential to reorder the clients which in some applications can be problematic. For example, in a traditional queuing system like the one used in the routers of a network, whenever a packet (client) is promoted or demoted from one QoS class to another QoS class then this may result in a reordering in either the same node in which the remark occurred or in a downstream node. The reordering of packets can be problematical as will be discussed next with respect to the network 100 shown in FIG. 1.
Referring to FIG. 1 (PRIOR ART), there is shown an exemplary network 100 which has a source computer 102 (user 102) that communicates with a destination computer 104 (user 104) via multiple routers/nodes 106 (only 9 routers/nodes 106 shown). Each router 106 includes a queuing system 108 with a queue 110 and a scheduler 112 that implements a traditional queuing method 114. An example of the operation of the traditional QoS method 114 is described next with respect to two of the routers 106′ and 106″. Assume three packets are received at the router 106′ in the order 1, 2, 3. The first and the third packets belong to the same flow (e.g. Transmission Control Protocol (TCP) flow) and have a ‘lower precedence’ QoS class than the second packet which belongs to another flow. As such, packets 1 and 3 are stored in a lower precedence queue than packet 2. Assume packets 2 and 3 arrive at the time when packet 1 was being transmitted to router 106″. After packet 1 is transmitted, the scheduler 112 in router 106′ schedules packet 2 to go after packet 1 since packet 2 has a higher precedence class than packet 3. Assume also that packet 3, having complied with a certain policy, was promoted by the scheduler 112 in router 106′ to a higher precedence class. In this example, the packets are transmitted in the order 1, 2, 3 to the downstream router 106″.
At the downstream router 106″, packet 1 waits in the lower precedence queue to be scheduled for transmission. Assume, that packet 1 finds packet 0 being transmitted so it has to wait. While packet 1 is waiting, packets 2 and 3 are received and queued in the higher precedence class. Upon completion of the transmission of packet 0, packets 2 and 3 are scheduled to go next since they are of higher precedence than packet 1. Notice that packets 1 and 3, which belong to the same flow, got reordered in the downstream router 106″. This reordering of packets 1 and 3 is not desirable and strongly discouraged for the reasons discussed next.
The reordering of packets is strongly discouraged because of the high complexity and high cost associated with the handling of reordered packets. For instance, if the packets are reordered then some higher layer protocols, like TCP for example, suffer a severe performance impact since out-of-order packets indicate packet loss and therefore congestion. This problem is discussed in greater detail in the following documents (the contents of which are incorporated by reference herein):    [1] S. Bohacek, J. P. Hespanha, J. Lee, C. Lim, K. Obraczka “TCP-PR: TCP for Persistent Packet Reordering”, Proceedings of the 23rd International Conference on Distributed Computing Systems, May 2003.    [2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Whang, and W. Weiss “An architecture for differentiated services”, RFC 2475, 1998.    [3] J. Heinanen, F. Baker, W. Weiss, J. Wroclawski “Assured Forwarding PHB Group”, RFC 2597, June 1999.In fact, in some network technologies (e.g., Asynchronous Transfer Mode (ATM)), it is strictly prohibited to reorder packets.
As can be seen, the reordering of clients (packets) which belonged to the same flow or service class when they entered the network is not desired and may even be prohibited. This reordering problem becomes even more complex when packets come in batches (i.e. flows) which are labeled with the same QoS or precedence class and which merge with other packet batches (flows) within the same QoS queue. To address this reordering problem, the assignee of the present invention has developed a queuing technique that was discussed in the aforementioned co-pending U.S. patent application Ser. No. 10/936,314. This queuing technique is also discussed in detail below with respect to FIGS. 2 and 3.
Referring to FIGS. 2-3, there are respectively illustrated a diagram of an exemplary network 200 and a flowchart of the queuing method 300 that addresses the aforementioned reordering problem. The exemplary network 200 has a source computer 202 that communicates with a destination computer 204 via multiple routers/nodes 206 (only 9 routers/nodes 206 shown). Each router 206 includes a queuing system 208 with a queue 210 and a scheduler 212 which together implement the queuing method 300. The queuing method 300 eliminates packet reordering due to the alteration of a packet's QoS class within a flow while at the same time maintaining the QoS treatment of that flow.
An example highlighting the features of the operation of the QoS queuing method 300 is described next with respect to two routers 206′ and 206″. Assume three packets are received at the router 206′ in the order 1, 2, 3. The first and the third packets belong to the same flow (e.g. TCP flow) and have a ‘lower precedence’ QoS class than the second packet which belongs to another flow. As such, packets 1 and 3 are placed in a lower precedence queue than packet 2. Assume packets 2 and 3 arrive at the time when packet 1 was being transmitted to router 206″. After packet 1 is transmitted, the scheduler 212 in router 206′ schedules packet 2 to be transmitted first since it has a higher precedence class than packet 3. Assume also that packet 3, having complied with a certain policy, was promoted by the scheduler 212 in router 206′ to a higher precedence class. The altered packet 3, assuming originally it was in QoS class 1 and is now in QoS class 2 where QoS class 2 has higher precedence than QoS class 1, is marked (step 302) with a special indicator/token 216a. The special indicator/token 216a is used to identify the old QoS class (e.g., QoS class 1) of packet 3 as well as the new QoS class (e.g., QoS class 2). The special indicator/token 216a can also indicate that the class of service of packet 3 had been altered. In this example, the packets are transmitted in the order 1, 2, 3 to the downstream router 206″.
At the downstream router 206″, packet 1 waits in the lower precedence queue to be scheduled for transmission and assume packet 1 finds packet 0 being transmitted and has to wait. While packet 1 is waiting, packets 2 and 3 are received and packet 2 is queued in the higher precedence class. Then, the downstream router 206″ checks (step 304) the special indicator/token 216a in packet 3 and queues (step 306) packet in its original QoS class (e.g., QoS class 1) (note: packet 3 no longer has the special indicator/token 216a when it is queued in the old QoS class). The downstream router 206″ also fakes the presence of the “remarked” packet 3 in the new QoS class (e.g., QoS class 2) by allocating (step 308) a proxy packet 218 in the new QoS class (e.g., QoS class 2). This is done so that the scheduler 212 can allocate the servicing of another packet in the new QoS class (e.g., QoS class 2) when the time comes to service the proxy packet 218. In particular, once the proxy client 218 is scheduled to be serviced, the head-of-line packet 1 in the old QoS class (e.g., QoS class 1) is serviced (step 308) as a new QoS class-2 packet instead of the proxy client 218. Prior to exiting the downstream router 206″, the altered packet 1 is marked (step 310) as being a QoS class-2 packet by using the special indicator/token 216b. The special indicator/token 216b is used to identify the old QoS class (e.g., QoS class 1) of packet 1 as well as the new QoS class (e.g., QoS class 2). The special indicator/token 216b can also indicate that the class of service of packet 1 had been altered. In this example, the packets 1 and 3 which originally belonged to the same flow or QoS class (e.g., QoS class 1) did not get reordered but instead were transmitted in the proper order to another downstream router 206′″. This particular ordering of the packets 1 and 3 is desired.
To summarize the queuing method 300, it can be seen that the exemplary network 200 had a router 206′ and a downstream router 206″ which both implemented the QoS queuing method 300 where the router 206′ altered (remarked) a QoS class of a packet (client) which was associated with a group of packets (clients) in a manner such that after the downstream router 206″ received the altered packet and the associated packets it would not reorder the altered packet and the associated packets. To accomplish this, the router 206′ functioned to mark (step 302) the altered packet with a special indicator/token 216a that indicated the old QoS class and the new QoS class of the altered packet. Then after the altered packet was received at the downstream router 206″, the special indicator/token 216a was checked (step 304). The downstream router 206″ then queued (step 306) the altered packet (without the special indicator/token 216a) in the old QoS class and also queued the other packets in the same flow within the old QoS class. Thereafter, the downstream router 206″ allocated (step 308) a proxy client 218 in the new QoS class. Once the proxy client 218 was scheduled to be serviced, the downstream router 206″ serviced (step 310) a head-of-line packet which was selected from the packets queued in the old QoS class as being in the new QoS class instead of servicing and sending the proxy client 218 to another downstream router 206′″. The downstream router 206″ also functioned to mark (step 312) the head-of-line packet with a special indicator/token 216b that indicated the old QoS class and the new QoS class of the head-of-line packet before sending the marked head-of-line packet to another downstream node 206′″. The special indicator/token 216a and 216b described above can be a packet field value or a bit. For example, in Diffserv this particular packet field value or bit can be a ‘special’ DSCP (Differentiated Services Code Point) value that indicates for instance that this packet was AF2: Assured Forwarding 2 (A Diffserv Quality of Service Class) and now is AF1: Assured Forwarding 1 (A Diffserv Quality of Service Class).
Although this queuing system 208 and queuing method 300 works well to prevent the reordering of packets there is still a desire to have an improved queuing system and method that can more effectively ensure that packets are not reordered within the network. This particular need and other needs have been satisfied by queuing system and method of the present invention.